The approaches described in this section could be pursued, but are not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated herein, the approaches described in this section are not prior art to the claims in this application and are not admitted to be prior art by inclusion in this section.
Border Gateway Protocol (BGP) is a path vector routing protocol for inter-Autonomous System routing. The function of a BGP-enabled network element (a BGP host or peer) is to exchange network reachability information with other BGP-enabled network elements. The most commonly implemented version of BGP is BGP-4, which is defined in RFC1771 (published by the Internet Engineering Task Force (IETF) in March 1995).
To exchange routing information, two BGP hosts first establish a peering session by exchanging BGP OPEN messages. The BGP hosts then exchange their full routing tables. After this initial exchange, each BGP host sends to its BGP peer or peers only incremental updates for new, modified, and unavailable/withdrawn routes in one or more BGP UPDATE messages. A route is defined as a unit of information that pairs a network destination with the attributes of a network path to that destination. The attributes of the network path include, among other things, the network addresses (also referred to as address prefixes or just prefixes) of the computer systems along the path. In a BGP host, the routes are stored in a Routing Information Base (RIB). Depending on the particular software implementation of BGP, a RIB may be represented by one or more routing tables. When more than one routing table represents a RIB, the routing tables may be logical subsets of information stored in the same physical storage space, or the routing tables may be stored in physically separate storage spaces.
After exchanging route information, each BGP peer independently performs a series of calculations, including determining best paths among hosts, using the routing table information. In a process termed convergence, each BGP peer generates update messages to remote peers, and each peer eventually arrives at a complete set of usable routing information.
As defined in RFC1771, the structure of a BGP UPDATE message accommodates updates only to Internet Protocol version 4 (IPv4) unicast routes. The Multiprotocol Extension for BGP defined in RFC2858 (published by IETF in June 2000) accommodates updates to routing information for multiple Network Layer protocols, such as, for example, Internet Protocol version 6 (IPv6), Internetwork Packet eXchange (IPX), Appletalk, Banyan Vines, Asynchronous Transfer Mode (ATM), X.25, and Frame Relay. RFC2858 introduced two single-value parameters to accommodate the changes to the BGP UPDATE message structure: the Address Family Identifier (AFI) and the Subsequent Address Family Identifier (SAFI).
The AFI parameter carries the identity of the network layer protocol associated with the network address that follows next in the path to the destination. The SAFI parameter provides additional information about the type of the Network Layer Reachability Information that is included in a BGP UPDATE message, and the values defined for this parameter usually indicate a type of communication forwarding mechanism, such as, for example, unicast or multicast. While some of the AFI and SAFI values are reserved for private use, the AFI and SAFI values that can be commonly used by the public must be assigned through the Internet Assigned Numbers Authority (IANA). The AFI/SAFI combination is used by the software implementations of BGP to indicate the type of the BGP prefix updates, what format the prefix updates have, and how to interpret the routes included in the BGP UPDATE messages.
However, a problem with current BGP implementations is that convergence requires too much time because of the sheer number of routes that are stored in the routing tables of BGP peers. For example, in many service provider networks, the BGP tables stored by routers comprise a few hundred thousand prefixes. During the convergence phase, BGP peers need to exchange these thousands of prefixes with each other. Converging all these prefixes for all the different BGP address families takes in the order of minutes.
Thus, as BGP table sizes grow larger, there is an increasing need to improve BGP convergence times.
Further, there is an increasing need to improve overall convergence inclusive of the time it takes for traffic to begin forwarding.